/**
 * 重构字符串 使用栈的思想
 * 空间复杂度 O(n)
 * 时间复杂度 O(n)
 * @param s 
 * @param t 
 * @returns 
 */
function backspaceCompare(s: string, t: string): boolean {
    return tools(s)===tools(t)
    function tools(str:string):string{
        const arr = str.split(''),
            stack = [],
            length = arr.length;
        for(let i=0;i<length;i++){
            if(arr[i]!=='#'){
                stack.push(arr[i])
            }else{
                stack.length&&stack.pop()
            }
        }
        return stack.join('')
    }
};

/**
 * 双指针
 * @param s 
 * @param t 
 */
function backspaceCompareOther(s: string, t: string): boolean {
    let n = s.length-1,
        m = t.length-1,
        i=0,
        j=0;
    while(n>=0||m>=0){
        while(n>=0){
            if(s[n]==='#'){
                i++
                n--
            }else if(i>0){
                i--
                n--
            }else{
                break
            }
        }
        while(m>=0){
            if(t[m]==='#'){
                j++
                m--
            }else if(j>0){
                j--
                m--
            }else{
                break
            }
        }
        if(n>=0&&m>=0){
            if(s[n]!==t[m]) 
                return false
        }else {
            if(n>=0||m>=0){
                return false
            }
        }
        n--
        m--
    }
  
   return true
   
};